/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"

#include <stack>
#include <iostream>
using namespace std;

/*
// this function depends on buffer in NonLeafNode to be public
// change this back to private/protected and comment out this function after testing
void BTreeIndex::print(PageId pid, int height) {
    BTLeafNode leaf;
    BTNonLeafNode nonleaf;
    cout << "curr height: " << height << endl;
    if ( height == 1 ) {
        leaf.read(pid, pf);
        leaf.see_inside();
    } else {
        nonleaf.read(pid, pf); 
        nonleaf.see_inside();
        for (int i = 0; i <= nonleaf.getKeyCount(); i++) {
            PageId pid2;
            memcpy(&pid2, nonleaf.buffer + sizeof(int) + 2*sizeof(int)*i, sizeof(PageId));
            cout << "going to " << pid2 << " of height " << height - 1 << endl;
            print(pid2, height -1);
        }
     }
} 
*/


/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    this->mode = mode;
   	if (pf.open(indexname, mode) != 0) {
   		if ( mode == 'R' || mode == 'r') {return RC_FILE_READ_FAILED;}
   		if ( mode == 'W' || mode == 'w') {return RC_FILE_WRITE_FAILED;}
   	}	

    if ( mode == 'w' || mode == 'W' ) { return 0; }

    char buffer[1024];
    pf.read(0, buffer);
    memcpy(&rootPid, buffer, sizeof(PageId));
    memcpy(&treeHeight, buffer + sizeof(PageId), sizeof(int));

    return 0;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    RC rc;
    if (mode == 'W' || mode == 'w') {
        char buffer[1024];
        memcpy(buffer, &rootPid, sizeof(PageId));
        memcpy(buffer + sizeof(PageId), &treeHeight, sizeof(int));
        rc = pf.write(0, buffer);
        if ( rc != 0 ) {return rc;}
    }

	rc = pf.close();
	if (rc != 0 ) { return rc; }
  return 0;
}

// always make sure to use an unempty stack in the first call
RC BTreeIndex::insert_parent(int midkey, PageId child_id1, PageId child_id2) {
    
    BTNonLeafNode nonleafnode;  // parent node
    
    if( pid_traverse.empty() ) {    
        // need a new root 
        rootPid = pf.endPid();
        nonleafnode.initializeRoot(child_id1, midkey, child_id2);
        nonleafnode.write(rootPid, pf);
        treeHeight++;
        return 0;
    }

    PageId parent_id = pid_traverse.top();
    pid_traverse.pop();
    nonleafnode.read(parent_id, pf);

    if ( nonleafnode.insert(midkey, child_id2)!= 0 ) {
        // split and insert something to the parent of the parent 
        int nonleaf_midkey;
        BTNonLeafNode nonleaf_sibling;

        nonleafnode.insertAndSplit(midkey, child_id2, nonleaf_sibling, nonleaf_midkey);
        PageId sibling_id = pf.endPid();

        if ( nonleaf_sibling.write(sibling_id, pf) != 0) {
            return RC_FILE_WRITE_FAILED;
        }

        insert_parent(nonleaf_midkey, parent_id, sibling_id);
    }

    if ( nonleafnode.write(parent_id, pf)!= 0){ return RC_FILE_WRITE_FAILED; }

    return 0;
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    BTLeafNode leafnode;
    IndexCursor cursor;

    if ( locate(key, cursor) != 0 ) { return RC_INVALID_CURSOR; }

    leafnode.read(cursor.pid, pf);

    if ( leafnode.insert(key, rid) != 0 ) {
       // cout << "node is full and we have to split" << endl;
        // split 
        BTLeafNode sibling;
        int siblingKey;
        PageId sibling_id = pf.endPid();
        
        leafnode.insertAndSplit(key, rid, sibling, siblingKey);
        
        sibling.setNextNodePtr(leafnode.getNextNodePtr());
        
        if ( sibling.write(sibling_id, pf) != 0) { return RC_FILE_WRITE_FAILED; }
        
        leafnode.setNextNodePtr(sibling_id);

        insert_parent(siblingKey, cursor.pid, sibling_id);

    }
    if ( leafnode.write(cursor.pid, pf) != 0) { return RC_FILE_WRITE_FAILED; }

    // empty the stack
    while (!pid_traverse.empty()) {
        pid_traverse.pop();
    }

    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{

    if ( treeHeight == 0 ) {
        treeHeight++;

        cursor.pid = 1;
        cursor.eid = 0;

        rootPid = 1;
        BTLeafNode leafnode;
        leafnode.write(rootPid, pf);

    } else if ( treeHeight == 1 ) {
        // search root node/ only 1 leafnode.
        BTLeafNode leafnode;
        leafnode.read(rootPid, pf);
        //if ( leafnode.locate(searchKey, cursor.eid) != 0 ) { return RC_NO_SUCH_RECORD; }
        cursor.pid = rootPid;
    } else {
        // starting from root node, loop through.
        BTNonLeafNode nonleafnode;
        cursor.pid = rootPid;
        while(pid_traverse.size() + 1 < treeHeight) {
            pid_traverse.push(cursor.pid);
            nonleafnode.read(cursor.pid, pf);
            if ( nonleafnode.locateChildPtr(searchKey, cursor.pid) != 0 ) {return RC_NO_SUCH_RECORD; }
        }
       
        cursor.eid = 0;
    }
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    BTLeafNode leafnode;

    if ( leafnode.read(cursor.pid, pf) != 0) { return RC_FILE_READ_FAILED; }

    // read key, rid at cursor location
    if ( leafnode.readEntry(cursor.eid, key, rid) != 0 ) { return RC_NO_SUCH_RECORD; }

    // move cursor to next eid
    if ( cursor.eid < leafnode.getKeyCount() - 1) {
        cursor.eid++;
    } else {
        cursor.eid = 0;
        PageId next_node = leafnode.getNextNodePtr();
        if ( next_node == 0 ) { return RC_END_OF_TREE; }
        cursor.pid = next_node;
    }

    return 0;
}
